//
//  minimo.cpp
//  complexidade
//  http://br.spoj.pl/problems/MINIMO/
//  Created by Bruno Dias on 07/07/11.
//  Copyright 2011 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#define MAX 101

int custoMax = 200;

using namespace std;

int minimo(int a, int b) {
    return a < b ? a : b;
}

void preenche_tabela(int tabela[MAX][MAX][MAX], int n, int m) {
    int i, j;
    int vi, vj, w;
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= n; j++) {
            if (i != j) {
                tabela[0][i][j] = custoMax;
            } 
        }
    }
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &vi, &vj, &w);
        tabela[0][vi][vj] = minimo(tabela[0][vi][vj], w);
    }
    //Matriz predecessora
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= n; j++) {
            tabela[1][i][j] = tabela[0][i][j];
        }
    }
}

int main() {
    int i, j, k, n, m;
    int origem, destino, escala, c;
    int instancia = 1;
    int tabela[MAX][MAX][MAX];
    
    while (cin >> n >> m && !cin.eof()) {
        cout << "Instancia " << instancia++ << endl;
        preenche_tabela(tabela, n, m);
        

        //Algoritmo do floyd-warshall utilizando matriz tridimensional.
        for (k = 0; k <= n; k++) {
            for (i = 0; i <= n; i++) {
                for (j = 0; j <= n; j++) {
                    int aij = tabela[k][i][k] + tabela[k][k][j];
                    tabela[k][i][j] = minimo(tabela[k][i][j], aij);
                    if (k < n) {
                        tabela[k+1][i][j] = minimo(tabela[k][i][j], aij);
                    }
                }
            }
        }
        cin >> c;
        for (i = 0; i < c; i++) {
            cin >> origem >> destino >> escala;
            int saida = tabela[escala][origem][destino];
            if (saida == custoMax) {
                saida = -1;
            }
            cout << saida << endl;
        }
        cout << endl;
    }
    return 0;
}

